package AnswerOfComent;

import java.util.HashMap;
import java.util.Map;

/**
 * 实现一个LRU缓存，第一次做，旨在练习
 * LRU：当不得不淘汰某些数据的时候（通常是容量已经满了），选择最久未被使用的数据进行淘汰
 *
 * LRUCache(int capacity) ：以 正整数 作为容量capacity 初始化 LRU 缓存
 * int get(int key) ：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value)：如果关键字key 已经存在，则变更其数据值value ；
 *                               如果不存在，则向缓存中插入该组key-value 。如果插入操作导致关键字数量超过capacity ，
 *                               则应该 逐出 最久未使用的关键字。
 *
 */
public class Tencent_146_LRUCache {
    class Node {
        int k, v;
        Node l, r;
        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }
    int n;
    Node head, tail;
    Map<Integer, Node> map;
    public Tencent_146_LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.v;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.v = value;
        } else {
            if (map.size() == n) {
                // 因为每一次的操作都有refresh过，所以可以保证链表中最后一个是最久未使用的
                Node del = tail.l;
                map.remove(del.k);
                delete(del);
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        refresh(node);
    }

    // refresh 操作分两步：
    // 1. 先将当前节点从双向链表中删除（如果该节点本身存在于双向链表中的话）
    // 2. 将当前节点添加到双向链表头部
    void refresh(Node node) {
        delete(node);
        node.r = head.r;
        node.l = head;
        head.r.l = node;
        head.r = node;
    }

    // delete 操作：将当前节点从双向链表中移除
    // 由于我们预先建立 head 和 tail 两位哨兵，因此如果 node.l 不为空，则代表了 node 本身存在于双向链表（不是新节点）
    void delete(Node node) {
        if (node.l != null) {
            Node left = node.l;
            left.r = node.r;
            node.r.l = left;
        }
    }

}
